A cryptographic system is a computer system that uses cryptography, typically to secure or authenticate data communication between a pair of computing devices connected to one another through a data communication link in the system. Each computing device has a cryptographic unit with the processing capacity to implement one or more cryptographic protocols used to secure or authenticate the data communication. The cryptographic protocols typically perform arithmetic operations on the bit strings representing parameters, messages, or data in the protocols to produce a bit string representing the output from the protocol.
In a cryptographic system that employs a public-key scheme, each correspondent in the system utilizes a private key and a corresponding public key related to the private key by a mathematical function. The mathematical function presents a “difficult” mathematical problem to ensure that a private key of a correspondent cannot be obtained from the corresponding public key. An example of one such problem is the discrete logarithm problem over a finite field. A particularly robust and efficient public-key system based on the discrete logarithm problem makes use of points on an elliptic curve defined over a finite field. Such systems, referred to as elliptic curve cryptography (ECC) systems, offer high levels of security at faster computation time than other systems.
Public-key schemes allow for elegant signature algorithms that provide non-repudiation services. The ElGamal signature and its variants are one such group of signatures that is used in a public-key scheme based on the discrete logarithm problem. The ElGamal signature scheme and its variants are known in the art and are described, for example, in detail in Chapter 11 Section 11.5 of “Handbook of Applied Cryptography”, Menez et al., CRC Press, 1997, incorporated herein by reference.
The ElGamal signature scheme can be summarized as follows. Consider a cryptographic system having cryptographic parameters which include an appropriate prime number p and a generator α of the multiplicative group Z*p. A correspondent A has long-term private key d and corresponding long-term public key y=αd mod p. The computational unit of correspondent A performs the following steps to generate an ElGamal signature for a message m:                (a) select a random secret integer k, 1≦k≦p−2, with gcd(k, p−1)=1;        (b) compute a first signature component r=αk mod p;        (c) compute k−1 mod(p−1); and        (d) compute a second signature component s=k−1(h(m)−dr)mod(p−1) where h(•) is a cryptographic hash function.The signature generated is the pair (r, s).        
Variations of the ElGamal signature scheme exist and are known in the art. For example, such variations include the Digital Signature Algorithm (DSA), the Schnorr signature scheme, and ElGamal signatures with message recovery. Most of these variations involve slightly different forms of what is commonly referred to as the signing equation, that is, the equation used to compute the second signature component s in step (d) above. A popular variation of the ElGamal signature scheme is the Digital Signature Algorithm (DSA). In the DSA, the signing equation is s=k−1(h(m)+dr)mod q, where q is the order of a cyclic group in Z*p.
In elliptic curve cryptographic systems, a commonly used signature scheme is the Elliptic Curve Digital Signature Algorithm (ECDSA). A summary of the ECDSA is as follows. Assume correspondent A has a long-term private key d and a corresponding long-term public key D=dG, where G is a base point on the curve specified in the domain parameters. G will be assumed to have prime order n. Correspondent A therefore performs the following steps to generate an ECDSA signature for a message m:                (a) select a random secret ephemeral private key kεR[1,n−1] and calculate associated ephemeral public key K=kG;        (b) compute a first signature component r=f(K)= xKmod n where xK is the integer representation of the first coordinate (also sometimes called the x-coordinate) of elliptic curve point K; and        (c) compute a second signature component s=k−1(h(m)+dr)mod n where h(•) is a cryptographic hash function whose outputs have bit length no more than that of n.The signature generated is the pair (r,s).        
Cryptographic systems may be subject to side channel attacks, in which timing information, electromagnetic emissions, power usage, or other side channel information is used to try and determine a secret value utilized by the cryptographic unit during calculations. Multiplication in a computational unit of a cryptographic system is typically implemented using a series of additions. Therefore, when calculating the term dr in the signing equation, the long-term private key d is directly added to itself r times. Generally, the more operations in which long-term private key d is directly used, the greater the probability that this private key may be compromised by a side channel attack.
Moreover, interlopers who employ side channel attacks are generally aware that in generating ElGamal signatures and their variants the long-term private key d is only utilized in one step of the generation of the signature, that being in the calculation of the signature component s by way of the signing equation. Therefore, an interloper may try and use differential side channel analysis to obtain information about long-term private key d. That is, an interloper may try and obtain information from the side channel over the course of signing multiple messages and compare the differences between this information to try and obtain information about private key d. By analysing the differences between the information upon multiple uses of private key d (i.e. upon multiple signing operations), it may be possible to extract enough information about long-term private key d to compromise its secrecy. The more operations in which long-term private key d is directly used in each signing operation, the greater the probability that differential side channel analysis may compromise private key d.